package leetcode_500;

import java.util.Arrays;

/**
 *@author 周杨
 *MatchsticksToSquare_473 给定一个数组的火柴长度大小 问能否拼凑出一个正方形
 *describe:用DFS AD 47%
 *2018年8月30日 上午11:37:01
 */
public class MatchsticksToSquare_473_ {
	
	/**
	 * describe:排序后深搜 AC 47%
	 * 2018年8月30日 上午11:36:41
	 */
	public boolean makesquare(int[] nums) {
        if (nums==null || nums.length<4) return false;
        int sideLen = 0;
        for (int num : nums) {
            sideLen += num;
        }
        if (sideLen % 4 != 0) return false;
        sideLen /= 4;
        Arrays.sort(nums);
        reverse(nums);
        return find(nums, new int[4], 0, sideLen);
    }
    
    public boolean find(int[] nums, int[] edges, int index, int sideLen) {
        if (index == nums.length) {
            if (edges[0]==sideLen && edges[1]==sideLen && edges[2]==sideLen)
                return true;
            else return false;
        }
        
        for (int i=0; i<4; i++) {
            if (edges[i]+nums[index] > sideLen) continue;
            edges[i] += nums[index];
            if (find(nums, edges, index+1, sideLen)) return true;
            edges[i] -= nums[index];
        }
        return false;
    }
    
    public void reverse(int[] nums) {
        int l=0, r=nums.length-1;
        while (l < r) {
            int temp = nums[l];
            nums[l] = nums[r];
            nums[r] = temp;
            l++;
            r--;
        }
    }
	
	
	/**
	 * describe:AC 5% 深度优先遍历 也就是回溯 暴力O（n^3）
	 * 2018年8月30日 上午11:35:58
	 */
	public boolean makesquare2(int[] nums) {
        if (nums == null || nums.length < 4) return false;
        int sum = 0;
        for (int num : nums) sum += num;
        if (sum % 4 != 0) return false;
        
        return dfs(nums, new int[4], 0, sum / 4);
    }
    
    /**
     * describe:每次分配index所在的火柴给第i个火柴
     * 2018年8月30日 上午11:34:59
     */
    private boolean dfs(int[] nums, int[] sums, int index, int target) {
        if (index == nums.length) {
            if (sums[0] == target && sums[1] == target && sums[2] == target) {
            return true;
            }
            return false;
        }
        
        for (int i = 0; i < 4; i++) {
            if (sums[i] + nums[index] > target) continue;//这个index不能给这个火柴
            sums[i] += nums[index];
            if (dfs(nums, sums, index + 1, target)) return true;//给这个火柴试试
            sums[i] -= nums[index];//给下一个火柴
        }
        
        return false;
    }
	
	
	/**
	 * describe:这种贪心算法 思想错误 333344445555过不了
	 * 2018年8月29日 下午5:10:18
	 */
	public boolean makesquare1(int[] nums) {
        if(nums.length<4)
        	return false;
        int sum=0;
        for(int num:nums)
        	sum+=num;
        if(sum%4!=0)
        	return false;
        int med=sum/4;
        Arrays.sort(nums);
        int i=0,j=nums.length-1;
        while(j>=i) {
        	if(nums[j]==med)
        		--j;
        	else if(nums[j]>med)
        		return false;
        	else {
        		nums[j]+=nums[i];
        		++i;
        	}
        }
        return true;
    }
	
	
}
